/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

import org.junit.Test;

/**
 * <p>查找数组中第k个最大元素</p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月22日
 */
public class KthLargestElementInArray {
    public int findKthLargest(int[] nums, int k) {
        if(nums==null || k<=0){
            return -1;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        for(int num:nums){
            if(heap.size()<k){
                heap.add(num);
            }else{
                if(heap.peek()<num){
                    heap.poll();
                    heap.add(num);
                }
            }
        }
/*        for(int i=0;i<k-1;i++){
            System.out.println("size:"+heap.poll());
        }*/
        return heap.poll();
    }
    @Test
    public void testCase(){
        int []nums = {3,2,1,5,6,4};
        int k = 2;
        int largest = findKthLargest(nums, k );
        System.out.println("Largest:"+largest);
    }
}
